# You are given two linked lists representing two non-negative numbers.
# The digits are stored in reverse order and each of their nodes contain a single digit.
# Add the two numbers and return it as a linked list.

# Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
# Output: 7 -> 0 -> 8

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

#155ms
class Solution_1(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        array1 = [l1.val] #l1数组
        array2 = [l2.val] #l2数组

        #将l1转换为数组
        while l1.next != None:
            l1 = l1.next
            array1.append(l1.val)

        #将l2转换为数组
        while l2.next != None:
            l2 = l2.next
            array2.append(l2.val)

        #将array2的每一位加到array1相应位置上
        for i in range(0, len(array2)):
            if i >= len(array1): #如果array2位数大于array1
                array1.append(array2[i]) #将array2多出的位数添加到array1尾
                continue

            array1[i] += array2[i]  #对应位的数相加

        addition = 0 #进位
        for i in range(0, len(array1)):
            if array1[i] > 9: #如果相加结果溢出
                addition = 1 #设置进位
                array1[i] -=10 #溢出结果减10
            else:
                addition = 0 #没有溢出则进位归零

            if addition == 1: #如果存在进位
                if i == len(array1) - 1: #如果是最大位数
                    array1.append(1) #结果添加一位
                else:
                    array1[i+1] += 1 #对下一位加1

        resultNode = ListNode(array1[0]) #最终结果
        node = resultNode #节点

        #将数组转换为链表
        for i in range(1, len(array1)):
            node.next = ListNode(array1[i])
            node = node.next

        return resultNode

#126ms  O(max(m,n))/O(max(m,n))
class Solution_2(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        addition = 0 #进位
        value1 = l1.val #l1当前节点值
        value2 = l2.val #l2当前节点值

        result = ListNode(0) #结果
        node = result #节点

        while True:
            cValue = addition + value1 + value2 #l1、l2和进位相加

            if cValue > 9: #如果结果溢出
                cValue -= 10 #结果减10
                addition = 1 #设置进位
            else:
                addition = 0 #否则进位归零

            node.val = cValue #设置结果节点为计算结果

            #判断l1是否为空且存在下一个节点
            if l1 != None and l1.next != None:
                l1 = l1.next #获取l1下一个节点
                value1 = l1.val #获取l1下一个节点值
            else:
                l1 = None #l1下一个节点为空
                value1 = 0 #l1下一个节点值为0

            if l2 != None and l2.next != None:
                l2 = l2.next
                value2 = l2.val
            else:
                l2 = None
                value2 = 0

            #如果没有进位且l1和l2下一个节点都为空
            if addition == 0 and l1 == None and l2 == None:
                return result

            node.next = ListNode(0) #初始化 结果链表 的下一个节点
            node = node.next #获取 结果链表 下一个节点




#test
solution = Solution_1()

l1 = ListNode(9)
l1.next = ListNode(9)
# l1.next.next = ListNode(3)

l2 = ListNode(9)
# l2.next = ListNode(6)
# l2.next.next = ListNode(4)

result = solution.addTwoNumbers(l1, l2)

print("\n", "-----------------------------------------", "\n")

print(result.val)
while result.next != None:
    result = result.next
    print(result.val)

print("\n", "-----------------------------------------", "\n")